\documentclass{article}
\usepackage[english]{babel}
\usepackage[letterpaper,top=2cm,bottom=2cm,left=3cm,right=3cm,marginparwidth=1.75cm]{geometry}
\usepackage{xeCJK}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage[colorlinks=true, allcolors=blue]{hyperref}
\usepackage{listings}
\usepackage{float}
\usepackage[colorlinks=true, allcolors=blue]{hyperref}
\usepackage{xcolor}
\usepackage{subfigure}%并排子图 共享标题 有子标题
\usepackage{array}
\usepackage{amsmath}
\usepackage{graphicx}
\graphicspath{images/}
\title{堆排序和快速排序}
\author{舒开宸 3210103247}

\begin{document}

\maketitle

\section{测试结果}
\begin{figure}[hp]
  \centering
  \subfigure{
    \label{fig:subfig:onefunction} 
    \includegraphics[width=6cm]{images/1.png}}
  \hspace{0.5in} % 两图片之间的距离
  \subfigure{
    \label{fig:subfig:twofunction} 
    \includegraphics[width=6cm]{images/2.png}}
  \caption{数据量分别为100000和200000}
  \label{fig:twopicture} 
\end{figure}
\begin{figure}[hp]
  \centering
  \subfigure{
    \label{fig:subfig:onefunction} 
    \includegraphics[width=6cm]{images/3.png}}
  \hspace{0.5in} % 两图片之间的距离
  \subfigure{
    \label{fig:subfig:twofunction} 
    \includegraphics[width=6cm]{images/4.png}}
  \caption{数据量分别为300000和400000}
  \label{fig:twopicture} 
\end{figure}
\begin{figure}[hp]
    \centering
    \includegraphics[width=7cm]{images/5.png}
    \caption{数据量为500000}
    \label{fig:my_label}
\end{figure}  
\clearpage
\section{分析}
从运行结果来看，快速排序效率要优于堆排序，堆排序有建堆过程，在堆排序过程每次都移除最小的元素，将最大的元素放道堆顶，然后再做下沉，会有很多不必要的比较，这种比较随数据规模的增大是和$Nlog(N)$相关的。而快速排序在做的元素的比较对换是不会超过整个向量的逆序数的个数，所以在有序的情况下对换的过程会大大减少，趋向O(N)的复杂度。
\section{快速排序的改进}
在有序的情况下可以判断子序列是否已经是排好序的序列，如果已经排好序则跳出函数，这样就可以减少不必要的判断。
测试结果如下，可见当有序程度够大时运行效率有明显提升
\begin{figure}[hp]
    \centering
    \includegraphics[width=12cm]{images/6.png}
    \caption{同数据量未加判断函数}
    \label{fig:my_label}
\end{figure} 
\begin{figure}[hp]
    \centering
    \includegraphics[width=12cm]{images/7.png}
    \caption{同数据量增加判断函数}
    \label{fig:my_label}
\end{figure}
\end{document}
